package Sort;

import com.sun.scenario.effect.impl.sw.java.JSWColorAdjustPeer;

public class sort6 {
    //快速排序
    public static void main(String[] args) {
        int[] arr = {10, 5, 21, 6, 7, 2, 9, 11, 3, 1};
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        quickSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    //先确定一个基准值，把小于基准值的放左边，把大于基准值的放右边
    //再把基准值和数组中间下标交换
    //再递归基准的左边和右边（这过程类似于二叉树的前序遍历）
    private static void quickSort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }

    private static void quick(int[] arr, int start, int end) {
        //只有一个结点或没有结点的情况
        if (start >= end) {
            return;
        }
        //三数取中法(属于一种优化)
        int mid = midofthree(arr, start, end);
        swap(arr,mid,start);

        int piovt = partition2(arr, start, end);

        quick(arr, 0, piovt - 1);
        quick(arr, piovt + 1, end);


    }

    //Hoare法
    private static int partition1(int[] arr, int left, int right) {
        //先确立最左边的值为基准值
        int key = arr[left];
        //记录下一开始left的值
        int i = left;
        while (left < right) {
            //这里是预防arr[right]的值一直大于key
            //arr[right] >= key这个条件里的=号必须要取否则如果两个值相同就会一直换
            while (left < right && arr[right] >= key) {
                right--;
            }
            while (left < right && arr[left] <= key) {
                left++;
            }
            swap(arr, left, right);
        }
        swap(arr, i, left);
        return left;
    }


    //挖坑法
    private static int partition2(int[] arr, int left, int right) {
        //先确立最左边的值为基准值
        int key = arr[left];

        while (left < right) {
            //这里是预防arr[right]的值一直大于key
            //arr[right] >= key这个条件里的=号必须要取否则如果两个值相同就会一直换
            while (left < right && arr[right] >= key) {
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] <= key) {
                left++;
            }
            arr[right] = arr[left];


        }
        arr[left] = key;
        return left;
    }
    //三数取中法
    private static int midofthree(int[] arr, int start, int end) {

        int mid = (start + end) / 2;
        if (arr[start] < arr[end]) {
            if (arr[mid] > arr[end]) {
                return end;
            } else if (arr[mid] < arr[start]){
                return start;
            }
            else{
                return mid;
            }
        } else {
            if (arr[mid] > arr[start]) {
                return start;
            } else if (arr[mid] < arr[end]){
                return end;
            }
            else{
                return mid;
            }

        }
    }


    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }
}
